package com.algorithm.list_node;

import com.dataconsruct.ListNode;

/**
 * 合并K个有序链表
 *
 *      给定一个链表数组，每个链表都已经按升序排列。
 *      请将所有链表合并到一个升序链表中，返回合并后的链表。
 *
         * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
         * 输出：[1,1,2,3,4,4,5,6]
         * 解释：链表数组如下：
         * [
         *   1->4->5,
         *   1->3->4,
         *   2->6
         * ]
         * 将它们合并到一个有序链表中得到。
         * 1->1->2->3->4->4->5->6
 *
 * https://leetcode.cn/problems/vvXgSW/description/
 *
 * @author gatts, 2025/9/22 19:13
 */
public class MergeKListsTest {

    public static void main(String[] args) {
        ListNode[] lists = new ListNode[]{
                new ListNode(1, new ListNode(4, new ListNode(5))),
                new ListNode(1, new ListNode(3, new ListNode(4))),
                new ListNode(2, new ListNode(6))};

        ListNode mergedKLists = new MergeKListsTest().mergeKLists(lists);
        System.out.println(mergedKLists);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;
        for (ListNode node : lists) {
            tail = mergeTwoLists(tail, node);
        }
        return dummyHead.next;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        /* 虚拟头 */
        ListNode dummyHead = new ListNode(-1);
        /* a,b两个链表的指针 */
        ListNode cur1 = a, cur2 = b;
        /* 随双指针移动的尾节点*/
        ListNode tail = dummyHead;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                tail.next = cur1;
                cur1 = cur1.next;
            }
            else if (cur1.val > cur2.val) {
                tail.next = cur2;
                cur2 = cur2.next;
            }
            tail = tail.next;
        }

        tail.next = cur1 == null ? cur2 : cur1;
        return dummyHead.next;
    }
}
